using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
using System.IO;
using System.Text;
using UnityEngine.Tilemaps;

public class DynamicProgramming : MonoBehaviour
{
    public struct Point
    {
        public int x, y;
        public Point(int _x, int _y) {
            x = _x;
            y = _y;
        }
    }

    public class Node
    {
        public Point point;
        public Node parent;
        public double f, g, h;
    }

    public Tilemap map;
    public Button btn;
    private string filepath1;
    private string filepath2;
    private string filepath3;
    private string filepath4;
    private string filepath5;
    private Dictionary<Point, Node> open;
    private HashSet<Point> closed;

    // Start is called before the first frame update
    void Start()
    {
        filepath1 = @"C:\Users\caomb\Desktop\实训\代表点.txt";
        filepath2 = @"C:\Users\caomb\Desktop\实训\代表点路径.txt";
        filepath3 = @"C:\Users\caomb\Desktop\实训\矩阵.txt";
        filepath4 = @"C:\Users\caomb\Desktop\实训\父节点.txt";
        filepath5 = @"C:\Users\caomb\Desktop\实训\地图路径.txt";
        btn.onClick.AddListener(foo);
    }

    void foo()
    {
        ArrayList list = new ArrayList();
        using(StreamReader sr = new StreamReader(filepath1, Encoding.UTF8)) {
            string line;
            string[] tmp;
            int x = 0, y = 0;
            Vector3Int p = new Vector3Int(0, 0, 0);
            while(sr.Peek() >= 0) {
                line = sr.ReadLine();
                if(line.Length > 0) {
                    tmp = line.Split();
                    x = (int)Convert.ToDouble(tmp[0]);
                    y = (int)Convert.ToDouble(tmp[1]);
                    p = new Vector3Int(x, y, 0);
                    list.Add(p);
                }
            }
        }
        double[,] arr = new double[list.Count, list.Count];
        int[,] parent = new int[list.Count, list.Count];
        for(int i = 0; i < list.Count; i++) {
            for(int j = 0; j < list.Count; j++) {
                if(i == j) {
                    arr[i, j] = 0;
                } else {
                    arr[i, j] = -1;
                }
                parent[i, j] = -1;
            }
        }
        using(StreamWriter sw1 = new StreamWriter(filepath2, false)) {
            for(int i = 0; i < list.Count; i++) {
                for(int j = i+1; j < list.Count; j++) {
                    Vector3Int p1 = (Vector3Int)list[i];
                    Vector3Int p2 = (Vector3Int)list[j];
                    double dis = Calculate(new Point(p1.x, p1.y), new Point(p2.x, p2.y));
                    if(dis > 10 && j - i > 1) {
                        continue;
                    }
                    parent[i, j] = i;
                    sw1.Write(i);
                    sw1.Write(" ");
                    sw1.Write(j);
                    bool flag = false;
                    open = new Dictionary<Point, Node>();
                    closed = new HashSet<Point>();
                    Point des = new Point(p2.x, p2.y);
                    Node init = new Node();
                    init.point = new Point(p1.x, p1.y);
                    init.parent = null;
                    init.g = 0;
                    init.h = Calculate(init.point, des);
                    init.f = init.g + init.h;
                    open.Add(init.point, init);
                    while(open.Count > 0) {
                        Node min = GetMin(open);
                        Point p = min.point;
                        if(p.x == p2.x && p.y == p2.y) {
                            arr[i, j] = min.g;
                            sw1.Write("\n");
                            Node node = min;
                            PathWritting1(sw1, node);
                            sw1.Write("\n");
                            flag = true;
                            break;
                        }
                        open.Remove(min.point);
                        closed.Add(min.point);
                        for(int k = -1; k <= 1; k++) {
                            for(int h = -1; h <= 1; h++) {
                                if(k == 0 && h == 0) {
                                    continue;
                                }
                                if(k == 0 || h == 0) {
                                    AddToOpen(new Point(p.x+k, p.y+h), new Point(p2.x, p2.y), min, 0);
                                } else {
                                    AddToOpen(new Point(p.x+k, p.y+h), new Point(p2.x, p2.y), min, 1);
                                }
                            }
                        }
                    }
                    if(flag == false) {
                        sw1.WriteLine(-1);
                    }
                }
            }
        }
        for(int i = 0; i < list.Count; i++) {
            for(int j = i+1; j < list.Count; j++) {
                for(int k = j+1; k < list.Count; k++) {
                    if(arr[i, j] != -1 && arr[j, k] != -1 && i != k) {
                        string sum = (arr[i, j] + arr[j, k]).ToString("N1");
                        if(arr[i, k] == -1 || arr[i, k] > Convert.ToDouble(sum)) {
                            parent[i, k] = j;
                            arr[i, k] = Convert.ToDouble(sum);
                        }
                    }
                }
            }
        }
        using(StreamWriter sw2 = new StreamWriter(filepath3, false)) {
            for(int i = 0; i < list.Count; i++) {
                for(int j = 0; j < list.Count; j++) {
                    sw2.Write(arr[i, j]);
                    sw2.Write(" ");
                }
                sw2.Write("\n");
            }
        }
        using(StreamWriter sw3 = new StreamWriter(filepath4, false)) {
            for(int i = 0; i < list.Count; i++) {
                for(int j = 0; j < list.Count; j++) {
                    sw3.Write(parent[i, j]);
                    sw3.Write(" ");
                }
                sw3.Write("\n");
            }
        }
        using(StreamWriter sw4 = new StreamWriter(filepath5, false)) {
            for(int i = 0; i < list.Count; i++) {
                for(int j = i+1; j < list.Count; j++) {
                    sw4.WriteLine(i + " " + j);
                    PathWritting2(sw4, i, j, parent);
                    sw4.Write(j);
                    sw4.Write("\n");
                }
            }
        }
    }

    void PathWritting1(StreamWriter sw, Node node) {
        if(node != null) {
            PathWritting1(sw, node.parent);
            sw.Write("(");
            sw.Write(node.point.x);
            sw.Write(",");
            sw.Write(node.point.y);
            sw.Write(")");
            sw.Write(" ");
        }
    }

    void PathWritting2(StreamWriter sw, int i, int j, int[,] parent) {
        if(parent[i, j] != -1) {
            PathWritting2(sw, i, parent[i, j], parent);
            sw.Write(parent[i, j]);
            sw.Write(" ");
        }
    }

    double Calculate(Point p1, Point p2)
    {
        int x1 = p1.x, x2 = p2.x, y1 = p1.y, y2 = p2.y;
        int offsetX = Math.Abs(x1 - x2), offsetY = Math.Abs(y1 - y2);
        int square = offsetX * offsetX + offsetY * offsetY;
        double res = Math.Pow(square, 0.5);
        return res;
    }

    Node GetMin(Dictionary<Point, Node> open)
    {
        Node min = null;
        foreach(var node in open) {
            if(min == null || node.Value.f < min.f) {
                min = node.Value;
            }
        }
        return min;
    }

    void AddToOpen(Point p1, Point p2, Node parent, int flag)
    {
        if(map.HasTile(new Vector3Int(p1.x, p1.y, 0)) && !closed.Contains(p1)) {
            Node n = new Node();
            n.point = p1;
            n.parent = parent;
            if(flag == 0) {
                n.g = parent.g + 1;
            } else {
                n.g = parent.g + 1.4;
            }
            n.h = Calculate(p1, p2);
            n.f = n.g + n.h;
            if(open.ContainsKey(p1)) {
                if(n.f < open[p1].f) {
                    open[p1] = n;
                }
            } else {
                open.Add(p1, n);
            }
        }
    }

    // Update is called once per frame
    void Update()
    {
        
    }
}
